package Sort;

public class MergeSort {

    public static void sort(int[] arr){
        recursion(arr,0,arr.length-1);
    }

    private static void recursion(int[] arr,int left,int right){
        if (left < right){
            int mid = (left + right) >>> 1;
            recursion(arr,left,mid);
            recursion(arr,mid+1,right);
            merge(arr,left,mid,right);
        }
    }

    private static void merge(int[] arr,int left,int mid ,int right){
        int[] temp = new int[right - left + 1];
        int k = 0;
        int i = left;
        int j = mid + 1;

        while (i <= mid && j <= right){
            if (arr[i] < arr[j]){
                temp[k] = arr[i];
                i++;
            }else {
                temp[k] = arr[j];
                j++;
            }
            k++;
        }

        if (i <= mid){
            for (int l = i; l <= mid; l++) {
                temp[k] = arr[l];
                k++;
            }
        }else {
            for (int l = j; l <= right ; l++) {
                temp[k] = arr[l];
                k++;
            }
        }

        for (int l = 0; l <= temp.length - 1 ; l++) {
            arr[left + l] = temp[l];
        }
    }
}
